home *** CD-ROM | disk | FTP | other *** search
- /* Figure 1 - Minimal Binary Tree Program - */
-
- #include <stdlib.h>
- #include <stdio.h>
-
-
- /* Tree Node Definition */
-
- typedef struct node {
- struct node *left;
- struct node *right;
- char key;
- }node;
-
-
- /* Recursive Minimal Tree Insertion Function */
-
- node *tree_insert(node *root, node *new_node)
- {
- if(! root) {
- root = (node *) calloc(1, sizeof(node));
- root->key = new_node->key;
- return root; /* return pointer to new memory block */
- }
- if(new_node->key == root->key) /* if ==, return */
- return root;
- else if(new_node->key < root->key) /* if <, go left */
- root->left = tree_insert(root->left, new_node);
- else /* else go right */
- root->right = tree_insert(root->right, new_node);
-
- return root;
- }
-
- /* Recursive Minimal Tree In-Order Traversal Function */
-
- void tree_trace(node *root)
- {
- if(! root)
- return;
- tree_trace(root->left);
- printf("\n%c", root->key);
- tree_trace(root->right);
- }
-
- /* Minimal Tree Test Driver */
-
- void main(void)
- {
- char c, m = 'm';
- node *tree_root = NULL;
- node this_node = { NULL, NULL, '\0' };
-
- this_node.key = m;
- tree_root = tree_insert(tree_root, &this_node);
-
- for(c = '\x1';c < '\x5';c++) {
- this_node.key = m + c;
- tree_insert(tree_root, &this_node);
- this_node.key = m - c;
- tree_insert(tree_root, &this_node);
- }
- tree_trace(tree_root);
- printf("\n");
- exit(0); /* minimal, so let exit() free the dynamic memory */
- }
-